package org.xqh.study.leetcode.algorithm.linkedlist;

import org.xqh.study.leetcode.algorithm.linkedlist.RemoveNthFromEnd.ListNode;

/**
 * @ClassName MergeLinkListUtils
 * @Description 合并两个 有序链表
 * @Author xuqianghui
 * @Date 2021/2/5 22:13
 * @Version 1.0
 */
public class MergeLinkListUtils {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1, new ListNode(3, new ListNode(5, new ListNode(6))));
        ListNode node2 = new ListNode(2, new ListNode(4, new ListNode(6, new ListNode(8))));
        mergeTwo(node1, node2);
    }

    /**
     * 合并两个 有序链表
     * @param n1
     * @param n2
     * @return
     */
    public static ListNode mergeTwo(ListNode n1, ListNode n2){
        if(n1 == null || n2 == null){
            return n1 == null ? n2 : n1;
        }
        ListNode head =  new ListNode();//定义 一个 头数组

        ListNode tmp = head, tmp1 = n1, tmp2 = n2;
        while (tmp1 != null && tmp2 != null){
            if(tmp1.val <= tmp2.val){
                tmp.next = tmp1;
                tmp1 = tmp1.next;
            }else {
                tmp.next = tmp2;
                tmp2 = tmp2.next;
            }
            tmp = tmp.next;
        }
        tmp.next = tmp1 == null ? tmp2 : tmp1;
        return head.next;
    }
}
